package com.cwj.lab5.字符串.模式匹配;

public class StrIndexOf {
    int BF(String haystack, String needle) {
        //java判别空串
        if (needle.length() == 0) {
            return 0;
        }
        if (haystack.length() < needle.length()) {
            return -1;
        }
        int i = 0, j = 0;
        while (i < haystack.length() && j < needle.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i += 1;
                j += 1;
            } else {
                i -= (j - 1);
                j = 0;
            }
        }
        if (j >= needle.length()) {
            return i - needle.length();
        }
        return -1;
    }

    int KMP(String haystack, String needle) {
        //java判别空串
        if (needle.length() == 0) {
            return 0;
        }
        if (haystack.length() < needle.length()) {
            return -1;
        }
        int[] nextArray = calculateNext(needle);
        int i = 0, j = 0;
        while (i < haystack.length() && j < needle.length()) {
            if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
                i += 1;
                j += 1;
            } else {
                j = nextArray[j];
            }
        }
        if (j >= needle.length()) {
            return i - needle.length();
        }
        return -1;
    }

    private int[] calculateNext(String needle) {
        //注意我们的next的含义是：next[i],是needle[0,i-1]字符串中，最大相同前后缀的下一个元素
        //参考：https://hsuloong.github.io/algorithms-design/string-pattern-match-kmp.html
        int[] nextArray = new int[needle.length()];
        int j = -1;
        //注意：next数组的第一个位置原来是没有用的，后面就可以换为-1，变kmp匹配是可以被使用
        nextArray[0] = -1;
        for (int i = 0; i < needle.length() - 1; ) {
            //其都是通过比较i,j来更新i+1的
            if (j == -1 || needle.charAt(j) == needle.charAt(i)) {
                i += 1;
                j += 1;
                if (needle.charAt(i) == needle.charAt(j)) {
                    nextArray[i] = nextArray[j];
                } else {
                    nextArray[i] = j;
                }
            } else {
                //回溯
                j = nextArray[j];
            }
        }
        return nextArray;
    }
}

class Solution {
    public int strStr(String haystack, String needle) {
        StrIndexOf indexOf = new StrIndexOf();
        return indexOf.BF(haystack, needle);
    }
}
